package LeetCode算法.统计素数个数;

import java.util.Scanner;

public class Count_PrimeNumber {
    public static void main(String[] args) {
        System.out.println("统计n以内的素数个数，输入n的值为：");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        System.out.println("暴力算法:");
        getNum(n);
        System.out.println();

        System.out.println("埃筛法:");
        eratosthenes(n);

    }

    /**********************************************************************/
    //暴力算法：一个数字一个数字去匹配，判断是否为素数
    public static void getNum(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            count += isPrime(i) ? 1 : 0;
        }
        System.out.println(n + "之内的素数个数有" + count + "个");
    }

    //判断是否为素数
    public static boolean isPrime(int x) {
        /*没有必要比较x-2次，将i<x改为i * i <= x，相当于i<=根号x
         * 因为12=2*6或6*2，另一半就不需要了*/
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        System.out.println("已找到一个素数:" + x);
        return true;
    }

    /**********************************************************************/

    //埃筛法：素数 非素数(合数)
    public static void eratosthenes(int n) {
        boolean[] isPrime = new boolean[n]; //默认值为false,代表素数
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                count++;
                System.out.println("已找到一个素数:" + i);
                /*对埃筛法的优化为将j=2*i改为i*i*/
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = true;//标记合数为true
                }
            }
        }
        System.out.println(n + "之内的素数个数有" + count + "个");
    }
}
